public class BinarySearch {
    //第一个出现的数字和最后出现数字的索引
    //给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。
    //
    //如果数组中不存在目标值 target，返回 [-1, -1]。
    //
    //你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。
    //
    //
    //
    //示例 1：
    //
    //输入：nums = [5,7,7,8,8,10], target = 8
    //输出：[3,4]
    //示例 2：
    //
    //输入：nums = [5,7,7,8,8,10], target = 6
    //输出：[-1,-1]
    //示例 3：
    //
    //输入：nums = [], target = 0
    //输出：[-1,-1]
    public int[] searchRange(int[] nums, int target) {
        int[] ret =new int[2];
        ret[0]=ret[1]=-1;
        if(nums.length==0){
            return ret;
        }
        int left=0,right=nums.length-1;
        while(right>left){
            int mid=left+(right-left)/2;
            if(nums[mid]<target){
                left=mid+1;
            }else{
                right=mid;
            }
        }
        if(nums[left]==target){
            ret[0]=left;
        }else{return ret;}
        right=nums.length-1;
        while(right>left){
            int mid=left+(right-left+1)/2;
            if(nums[mid]<=target){
                left=mid;
            }else{
                right=mid-1;
            }
        }
        ret[1]=right;
        return ret;
    }
    //给你一个非负整数 x ，计算并返回 x 的 算术平方根 。
    //
    //由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。
    //
    //注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。
    //
    //
    //
    //示例 1：
    //
    //输入：x = 4
    //输出：2
    //示例 2：
    //
    //输入：x = 8
    //输出：2
    //解释：8 的算术平方根是 2.82842..., 由于返回类型是整数，小数部分将被舍去。
    class Solution {
        public int mySqrt(int x) {
            if(x==0){
                return 0;

            }
            long left=1,right=x;
            while(right>left){
                long mid=left+(right-left+1)/2;
                if(mid*mid<=x){
                    left=mid;
                }else{
                    right=mid-1;
                }

            }
            return (int)left;

        }
    }
    //给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
    //
    //请必须使用时间复杂度为 O(log n) 的算法。
    //
    //
    //
    //示例 1:
    //
    //输入: nums = [1,3,5,6], target = 5
    //输出: 2
    //示例 2:
    //
    //输入: nums = [1,3,5,6], target = 2
    //输出: 1
    //示例 3:
    //
    //输入: nums = [1,3,5,6], target = 7
    //输出: 4
    public int searchInsert(int[] nums, int target) {
        int left=0, right=nums.length-1;
        while(right>left){
            int mid=left+(right-left)/2;
            if(nums[mid]<target){
                left=mid+1;
            }else{
                right=mid;
            }
        }
        if(nums[right]<target){
            return right+1;
        }else{}
        return right;
    }
    //符合下列属性的数组 arr 称为 山峰数组（山脉数组） ：
    //
    //arr.length >= 3
    //存在 i（0 < i < arr.length - 1）使得：
    //arr[0] < arr[1] < ... arr[i-1] < arr[i]
    //arr[i] > arr[i+1] > ... > arr[arr.length - 1]
    //给定由整数组成的山峰数组 arr ，返回任何满足 arr[0] < arr[1] < ... arr[i - 1] < arr[i] > arr[i + 1] > ... > arr[arr.length - 1] 的下标 i ，即山峰顶部。
    //
    //
    //
    //示例 1：
    //
    //输入：arr = [0,1,0]
    //输出：1
    //示例 2：
    //
    //输入：arr = [1,3,5,4,2]
    //输出：2
    //示例 3：
    //
    //输入：arr = [0,10,5,2]
    //输出：1
    //示例 4：
    //
    //输入：arr = [3,4,5,1]
    //输出：2
    //示例 5：
    //
    //输入：arr = [24,69,100,99,79,78,67,36,26,19]
    //输出：2
    public int peakIndexInMountainArray(int[] arr) {
        int left=0, right=arr.length-1;
        while(right>left){
            int mid=left+(right-left+1)/2;
            if(arr[mid+1]>arr[mid]){
                left=mid;
            }else if(arr[mid-1]>arr[mid]){
                right=mid-1;
            }else{
                return mid;
            }
        }
        return left;
    }
}
